﻿using System.Text;

namespace LeetCodeProject._0001_1000._001_100._61_70._068;

public class Solution
{
    public IList<string> FullJustify(string[] words, int maxWidth)
    {
        IList<string> ans = new List<string>();
        int right = 0, n = words.Length;
        while (true)
        {
            int left = right; // 当前行的第一个单词在 words 的位置
            int sumLen = 0; // 统计这一行单词长度之和
            // 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格
            while (right < n && sumLen + words[right].Length + right - left <= maxWidth)
            {
                sumLen += words[right++].Length;
            }

            // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            if (right == n)
            {
                StringBuilder sb = Join(words, left, n, " ");
                sb.Append(Blank(maxWidth - sb.Length));
                ans.Add(sb.ToString());
                return ans;
            }

            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;

            // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
            if (numWords == 1)
            {
                StringBuilder sb = new StringBuilder(words[left]);
                sb.Append(Blank(numSpaces));
                ans.Add(sb.ToString());
                continue;
            }

            // 当前行不只一个单词
            int avgSpaces = numSpaces / (numWords - 1);
            int extraSpaces = numSpaces % (numWords - 1);
            StringBuilder curr = new StringBuilder();
            curr.Append(Join(words, left, left + extraSpaces + 1, Blank(avgSpaces + 1))); // 拼接额外加一个空格的单词
            curr.Append(Blank(avgSpaces));
            curr.Append(Join(words, left + extraSpaces + 1, right, Blank(avgSpaces))); // 拼接其余单词
            ans.Add(curr.ToString());
        }
    }

    // Blank 返回长度为 n 的由空格组成的字符串
    public string Blank(int n)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i)
        {
            sb.Append(' ');
        }

        return sb.ToString();
    }

    // Join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
    public StringBuilder Join(string[] words, int left, int right, string sep)
    {
        StringBuilder sb = new StringBuilder(words[left]);
        for (int i = left + 1; i < right; ++i)
        {
            sb.Append(sep);
            sb.Append(words[i]);
        }

        return sb;
    }
}